#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;

// 基本思路为:
// 从左往右遍历，找到右边第一个大于自己的塔
// 从右往左遍历，找到左边第一个大于自己的塔
// 然后再遍历两个数组，对上述两个数组中对应位置的塔的结果进行加加
// 最后返回结果
vector<int> signal_towers(vector<int>&out_put,vector<int>&height)
{
    // 创建一个栈装高度，并且结果数组，还有数组长度
    int n = height.size();
    vector<int>left(n,-1);
    vector<int>right(n,n);
    stack<int>s;
    vector<int>results(n,0);

    if (n <= 1) return results;

    // 获取每个元素左手边第一个比他大的数字 
    while (!s.empty())      s.pop();
    for (int i = 0;i < n;i++)
    {
        while (!s.empty()&&height[s.top()] < height[i])
            s.pop();

        // if (s.empty())
        // {
        //     left.push_back(-1);
        //     s.push(i);
        //     continue;
        // }
        // left.push_back(s.top());
        left[i] = s.empty()? -1:s.top();
        // 这个地方push的简直就是勾食
        s.push(i);
    }

    // 别忘了清空栈
    while (!s.empty())      s.pop();

    // 获取每个元素右边第一个比他大的数字
    for (int i = n-1;i >= 0;i --)
    {
        while (!s.empty()&&height[s.top()] < height[i])
        {
            s.pop();
        }
        right[i] = s.empty()? n:s.top();
        s.push(i);
    }

    // 别忘了反转这个right数组
    // reverse(right.begin(),right.end());

    // 最后一次遍历，确定每一位置的信号塔可以获得的能量
    for (int i = 0;i < n;i++)
    {
        // 判断是否为-1
        // 应该让左边第一个比他大的来加加才对，也就是重复方括号
        if (left[i] >=0)
        {
            results[left[i]] += out_put[i];
        }
        // 判断是否为n
        if (right[i] != n)
        {
            results[right[i]] += out_put[i];
        }
    }

    // 最后返回结果
    return results;
}

int main()
{
    vector<int>out_put = {1,1,3,1,1,2};
    vector<int>tower = {4,3,6,3,5,4};

    vector<int>res = signal_towers(out_put,tower);
    for (int i:res)
    {
        cout<<i<<" ";
    }

    return 0;
}
